#include <stdio.h>
#include <stdtype.h>
/*  Heapsort based on ideas of J.W.Williams/R.W.Floyd/S.Carlsson  */

#define SORTTYPE int
#define  data_i_LESS_THAN_(other)   (data[i] < other)
#define  MOVE_i_TO_free  { data[free]=data[i];  free=i; }

void sift_in(unsigned count, SORTTYPE *data, unsigned free_in, SORTTYPE next)
{
   unsigned  i;
   unsigned free = free_in;
   // sift up the free node 
   for (i=2*free;i<count;i+=i)
   {  if (data_i_LESS_THAN_(data[i+1]))  i++;
      MOVE_i_TO_free
   }
   // special case in sift up if the last inner node has only 1 child
   if (i==count)
      MOVE_i_TO_free
   // sift down the new item next 
   while( ((i=free/2)>=free_in)   &&  data_i_LESS_THAN_(next))
      MOVE_i_TO_free
   data[free] = next;
}

void heapsort(unsigned count, SORTTYPE *data)
{
   unsigned  j;
 
   if (count <= 1)  return;
   data-=1;   // map addresses to indices 1 til count
   // build the heap structure 
   for(j=count / 2; j; j -= 1) {
      SORTTYPE  next = data[j];
      sift_in(count, data, j, next);
   }

   // search next by next remaining extremal element
   for(j= count - 1; j; j -= 1) {
      SORTTYPE next = data[j + 1];
      data[j + 1] = data[1];   // extract extremal element from the heap
      sift_in(j, data, 1, next);
   }
}


int main(){
	int data[]={15,22,33,55,99,22,1,96};
	heapsort(8,data);
}
